package momo.multitree.algo;

import momo.multitree.structure.*;

import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedHashMap;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;


public class CostLastTree {
	private Log log = LogFactory.getLog(CostLastTree.class);
	
	private Tree sptTree;
	private Tree mstTree;
	
	private Graph graph;
	
	private Node root;
	
	private Tree lastTree;
	
	private HashMap<Node, Double> lastDistances =  new LinkedHashMap<Node, Double>();
	private HashMap<Node, Double> sptDistances = new LinkedHashMap<Node, Double>();
	
	public CostLastTree(Graph graph, Node root) {
		this.graph = graph;
		this.root = root;
		
		mstTree = new PrimMinSpanTree().mstCostTree(graph, root);
		lastTree = mstTree.clone();
		log.debug("mst tree:"+lastTree);
		sptTree = new CostShortestPath().optimumTree(graph, root);
		log.debug("spt tree:"+sptTree);
		
		sptDistances = computeDistances(sptTree);
		lastDistances = computeDistances(lastTree);
		
//		System.out.println("Start");
//		for(Node key: sptDistances.keySet())
//		{
//			Double dist = sptDistances.get(key);
//			System.out.println(key + ": " + dist);
//		}
	}
	
	protected HashMap<Node, Double> computeDistances(Tree tree) {
		HashMap<Node, Double> result = new LinkedHashMap<Node, Double>();
		result.put(root, 0.0);
		computeDistances(tree, result, root);
		return result;
	}
	
	private void computeDistances(Tree tree, HashMap<Node,Double> distances, Node parent) {
		double parentDistance = distances.get(parent);
		for (Edge edge : tree.getEdgesOfNode(parent)) {
			Node otherNode = edge.nextNode(parent);
			if (!distances.containsKey(otherNode))  {
				distances.put(otherNode, parentDistance + edge.getCost(parent));
				computeDistances(tree, distances, otherNode);
			}
		}
	}
	
	protected void addToSptPath(Tree tree, Node node, HashMap<Node, Double> distances) {
		
		if ( distances.get(node) == null )
			log.error("distance of node "+node.toString()+" is null");
		if ( sptDistances.get(node) == null )
			log.error("sptDist of node "+node.toString()+" is null");
		
		if (distances.get(node) > sptDistances.get(node)) {
			Node sptParent = sptTree.getParent(node);
			Node currParent = tree.getParent(node);
			log.debug("Replacing parent; child: "+node.getId()+" oldParent: "+currParent.getId()+" sptParent: "+sptParent.getId());
			addToSptPath(tree, sptParent, distances);
			Edge toCurrParent = tree.getEdge(node, currParent);
			tree.remove(toCurrParent);
			Edge toSptParent = graph.getEdge(node, sptParent);
			tree.add(toSptParent, sptParent);
			distances.put(node, distances.get(sptParent) + toSptParent.getCost(sptParent));
			
			//switchParent(tree, node, currParent, distances);
		}
		
	}
	
	protected void switchParent(Tree tree, Node formerChild, Node formerParent, HashMap<Node, Double> distances) {
		Edge edge = graph.getEdge(formerChild, formerParent);
		double adjDistance = distances.get(formerChild) + edge.getCost(formerChild);
		if (adjDistance < distances.get(formerParent)) {
			log.debug("switching edge; new edge: "+formerChild.getId()+"<-"+formerParent.getId());
			Node parentParent = tree.getParent(formerParent);
			Edge parentParentEdge = tree.getEdge(formerParent, parentParent);
			tree.remove(parentParentEdge);
			tree.add(edge, formerChild); // reverse the edge
			distances.put(formerParent, adjDistance);
			switchParent(tree, formerParent, parentParent, distances);
		}
		
	}
	/**
	 * newChild -> newParent
	 * @param newChild
	 * @param newParent
	 */
	protected void checkSwitchParent(Node newChild, Node newParent) {
		log.debug("checkSwitchParent: "+newChild.getId()+"<-?-"+newParent.getId());
				
		Tree tree = lastTree.clone();
		HashMap<Node, Double> treeDistances = new LinkedHashMap<Node, Double>(lastDistances);
		
		Node currParent = tree.getParent(newChild);
		Edge toCurrParent = tree.getEdge(newChild, currParent);
		tree.remove(toCurrParent);
		Edge toNewParent = graph.getEdge(newChild, newParent);
		
		if (tree.hasCycle(toNewParent)) {
			log.debug("switchParentCycle: "+newChild.getId()+"<-X-"+newParent.getId());
		}
		else {
			tree.add(toNewParent, newParent);
			double lastCost = lastTree.compCost(false);
			double currCost = tree.compCost(false);
			log.debug("switchPCosts: last: "+lastCost+" curr: "+currCost);
				
			if (currCost < lastCost) {
				log.debug("switchParentAccepted: "+newChild.getId()+"<---"+newParent.getId());	
				treeDistances.put(newChild, treeDistances.get(newParent) + toNewParent.getCost(newChild));
				lastTree = tree;
				lastDistances = treeDistances;
			}
			else 
				log.debug("switchParentRejected: "+newChild.getId()+"<-X-"+newParent.getId());
		}
					
		
	}
	
	protected void checkSpt(Node node) {
		log.debug("check spt for node: "+node.getId());
		Tree tree = lastTree.clone();
		HashMap<Node, Double> treeDistances = new LinkedHashMap<Node, Double>(lastDistances);
		
		addToSptPath(tree, node, treeDistances);
		
		double lastCost = lastTree.compCost(false);
		double currCost = tree.compCost(false);
		
		if (currCost < lastCost) {
			log.debug("spt path accepted");
			lastTree = tree;
			lastDistances = treeDistances;
		} else
			log.debug("spt path rejected");
		
		Collection<Node> currChildren = lastTree.getChildren(node);
		for (Node child : currChildren) {
			checkSpt(child);
			if ((node != root) && (!lastTree.getChildren(node).contains(child))) // try to reconnect by the former child
				checkSwitchParent(node, child);
		}
		
	}
	
	public Tree makeLast() {
		checkSpt(root);
		return lastTree;
	}

	public Tree getSptTree() {
		return sptTree;
	}

	public Tree getMstTree() {
		return mstTree;
	}

	public Tree getLastTree() {
		return lastTree;
	}
	
}
